The problem can be found at the following link: Question Link
For solving the "Subset Sum Problem," which is a classic dynamic programming problem. We have to determine if it's possible to partition an array into two subsets such that the sum of elements in both subsets is equal.
-
I start by calculating the total sum of all elements in the input array. If the sum is
odd
, it's impossible to partition the array into two subsets with equal sums, so I returnfalse
immediately. -
I create a 2D DP array
dp
, wheredp[i][target]
represents whether it's possible to achieve a sum oftarget
using the firsti
elements of the array. -
I use a recursive function
canPart
to fill the DP array. For each element in the array, I have two options:- Take the element into the subset by subtracting its value from the target sum.
- Skip the element and move to the next one.
- I recursively explore both options, and if I find a path that leads to the target sum, I set
dp[i][target]
to true.
- Time Complexity: The time complexity of this solution is
O(N * target)
, whereN
is the number of elements in the input array, and target is the target sum we are trying to achieve. - Auxiliary Space Complexity: The auxiliary space complexity is
O(N * target)
as well because of the DP array.
class Solution {
public:
bool canPart(int& N, int i, int arr[], int target, vector<vector<int>>& dp){
if(target == 0)
return true;
if(i >= N)
return false;
if(target >= arr[i]){
bool take = canPart(N,i+1,arr,target - arr[i], dp);
if(take)
return dp[i][target] = true;
}
bool notTake = canPart(N,i+1,arr,target, dp);
return dp[i][target] = notTake;
}
bool equalPartition(int N, int arr[])
{
int sum = 0;
for(int i = 0; i<N;++i){
sum += arr[i];
}
if(sum % 2 != 0) // If the sum is odd, it's impossible to partition into equal subsets.
return false;
int target = sum/2;
vector<vector<int>> dp(N,vector<int>(target+1,-1));
return canPart(N,0,arr,target, dp);
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.